import java.util.Arrays;
import java.util.Comparator;
import java.util.TreeMap;

/**
 * 知道工作的能力要求和薪水，给的能力可以获得的最高工资
 *
 * @author Liaorun
 */
public class ChooseWork {

    public static class Job {
        /**
         * 该工作的工资
         */
        public int money;
        /**
         * 能力要求
         */
        public int hard;

        public Job(int money, int hard) {
            this.money = money;
            this.hard = hard;
        }
    }

    public static class JobComparator implements Comparator<Job> {

        @Override
        public int compare(Job o1, Job o2) {
            return o1.hard != o2.hard ? (o1.hard - o2.hard) : (o2.money - o1.money);
        }
    }


    public static int[] getMoneys(Job[] jobs, int[] ability) {
        // 按照工作的难度排序，如果难度一样，工资高的在前面
        Arrays.sort(jobs, new JobComparator());

        // key: 工作的能力要求，工作的薪资
        // 记录可以选择的工作列表
        TreeMap<Integer, Integer> map = new TreeMap<>();

        map.put(jobs[0].hard, jobs[0].money);

        Job pre = jobs[0];

        for (int i = 1; i < jobs.length; i++) {
            // 1. 相同难度要求的工作只要第一个
            // 2. 更高难度的工作，必须要工作更高才加入可选则的工作列表
            if (jobs[i].hard != pre.hard && jobs[i].money > pre.money) {
                pre = jobs[i];
                map.put(pre.hard, pre.money);
            }
        }
        int[] ans = new int[ability.length];
        for (int i = 0; i < ability.length; i++) {

            // 获取最接近自己能力的工作
            Integer key = map.floorKey(ability[i]);
            // 如果能力太低或者可选的工作太少获取的报酬为0
            ans[i] = key != null ? map.get(key) : 0;
        }

        return ans;
    }
}
